package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
 * 二叉搜索树中的搜索
 * <p>
 * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
 * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
 */
public class Code14_SearchBST {
    public static void main(String[] args) {
        TreeNode searchTree = TreeNodeUtils.getBinarySearchTree();
        int num = 8;
        TreeNode treeNode = searchBST2(searchTree, num);
        TreeNodeUtils.printTree(treeNode);
    }

    public static TreeNode searchBST(TreeNode root, int num) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == num) {
                return cur;
            } else if (cur.val < num) {
                cur = cur.right;
            } else if (cur.val > num) {
                cur = cur.left;
            }
        }
        return cur;
    }

    public static TreeNode searchBST2(TreeNode root, int num) {
        TreeNode cur = root;
        if (root.val > num) {
            cur = searchBST2(cur.left, num);
        } else if (root.val < num) {
            cur = searchBST2(cur.right, num);
        } else {
            return cur;
        }
        return cur;
    }
}
